package com.kevinkk.dp;

/**
 * 给定两个单词 word1 和 word2 ，返回使得 word1 和  word2 相同所需的最小步数。
 * 每步 可以删除任意一个字符串中的一个字符。
 */

public class DeleteOperationForTwoStrings {
    class Solution {
        public int minDistance(String word1, String word2) {
            char[] c1 = word1.toCharArray(), c2 = word2.toCharArray();
            int[][] dp = new int[c1.length + 1][c2.length + 1];
            for (int i = 0; i <= c1.length; i++) dp[i][0] = i;
            for (int j = 0; j <= c2.length; j++) dp[0][j] = j;

            for (int i = 1; i <= c1.length; i++) {
                for (int j = 1; j <= c2.length; j++) {
                    if (c1[i - 1] == c2[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // 不相同，则需要多一步
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + 1;
                    }
                }
            }

            return dp[c1.length][c2.length];
        }
    }
}
